#include <cstdio>

int gcd( int a, int b )
{
    int rem;
    while ( b )
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

int main( )
{
    int n, a, b, i;
    scanf("%d", &n);
    while ( n-- )
    {
        scanf("%d%d", &a, &b);
        i = b + 1;
        while ( gcd( a, i ) != b )
            i++;
        printf("%d\n", i);
    }
    return 0;
}
